#ifndef STRINGCONSTRUCTION_H
#define STRINGCONSTRUCTION_H

#include <string>
using std::string;

int stringConstruction(const string &targetStr, int costOfClone,
                       int costOfAppend) {
  int totalCost = 0;                              // Total cost
  string intermediateResult;                      // Intermediate result
  size_t startPos = 0, endPos = targetStr.size(); // [startPos, endPos)

  auto computeCost = [](const string &targetStr, size_t &startPos,
                        size_t length, string &intermediateResult,
                        int costOfClone, int costOfAppend) -> int {
    if (costOfAppend * length < costOfClone) {
      for (size_t i = 0; i < length; ++i) {
        intermediateResult.push_back(targetStr[startPos + i]);
      }

      startPos += length;
      return costOfAppend * length;
    }

    intermediateResult.append(targetStr.substr(startPos, length));
    startPos += length;

    return costOfClone;
  };

  while (startPos != endPos) {
    size_t count = 0;
    while (startPos + count < endPos &&
           intermediateResult.find(targetStr.substr(startPos, count + 1)) !=
               string::npos)
      count++;

    if (count > 0) {
      size_t maxCount = count;
      size_t maxStartPos = startPos;

      for (size_t i = 1; i < count && i < 26; ++i) { // 26 - alphabet
        size_t innerCount = 0;

        string subStr;
        while (startPos + i + innerCount != endPos &&
               intermediateResult.find(
                   subStr = targetStr.substr(startPos + i, innerCount + 1)) !=
                   string::npos)
          innerCount += 1;

        if (innerCount > maxCount) {
          maxCount = innerCount;
          maxStartPos = startPos + i;
        }
      }

      if (count != maxCount) {
        totalCost += computeCost(targetStr, startPos, maxStartPos - startPos,
                                 intermediateResult, costOfClone, costOfAppend);
        count = maxCount;
      }
    }

    if (count == 0) {
      intermediateResult.push_back(targetStr[startPos]);
      totalCost += costOfAppend;
      startPos += 1;
    } else
      totalCost += computeCost(targetStr, startPos, count, intermediateResult,
                               costOfClone, costOfAppend);
  }

  return totalCost;
}

// do not write or edit anything below this line

#endif
